import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;




public class SearchingandSortingMethods implements Collection{
	private int[] ints;
	private int[] spotCheck;

	private int insertionStart=1;


	SearchingandSortingMethods(){
		ints = new int[3];
		newSpotCheck();
		/*spotCheck=new int[ints.length];
for (int i=0;i<3;i++)
{
ints[i]=getWhatToAdd();
}*/
	}

	public void newSpotCheck()
	{
		spotCheck=new int[ints.length+1];
	}


	public int[] getInts()
	{
		return ints;
	}

	public boolean add(Object whatToAdd){
		/*int[] newInts = new int[ints.length+1];
for(int i = 0; i < ints.length; i++)
newInts[i] = ints[i];
newInts[newInts.length-1] = (Integer)whatToAdd;
return true;*/
		newSpotCheck();
		int[] newInts = new int[ints.length+1];
		for(int i = 0; i < ints.length; i++)
			newInts[i] = getWhatToAdd();
		newInts[newInts.length-1] = (Integer)whatToAdd;
		ints=newInts;
		return true;
	}

	public int getWhatToAdd()
	{
		int whatToAdd = (int)(Math.random()*ints.length);
		while(spotCheck[whatToAdd] == 1)
			whatToAdd = (int)(Math.random()*ints.length);
		spotCheck[whatToAdd] = 1;
		return whatToAdd;
	}




	//BUBBLE SORT
	//this was bubbleSort1 before. why?
	public void bubbleSort() {
		int n = ints.length;
		for (int pass=1; pass < n; pass++) 
		{
			for (int i=0; i < n-pass; i++) 
			{
				if (ints[i] > ints[i+1]) 
				{
					int temp = ints[i];  ints[i] = ints[i+1];  ints[i+1] = temp;
				}
			}
			if(anythingExtra())
			{
				break;
			}
		}
	}


	public void selectionSort() 
	{
		for (int i=0; i<ints.length-1; i++) 
		{
			int minIndex=i;
			for (int j=i+1; j<ints.length; j++) 
			{
				if (ints[minIndex]>ints[j]) 
				{
					minIndex=j;
				}
			}
			if (minIndex!=i)
			{
				int temp = ints[i];
				ints[i] = ints[minIndex];
				ints[minIndex] = temp;
				if (anythingExtra())
				{
					break;
				}
			}
		}
	}


	public void insertionSort()
	{
		int j, key, i;
		for (j = insertionStart; j < ints.length; j++)
		{
			key = ints[j];
			for(i = j - 1; (i >= 0) && (ints[i] > key); i--)
			{
				ints[i+1] = ints[i];

			}
			ints[i+1] = key;
			if (anythingExtra())
			{
				insertionStart++;
				break;
			}

		}
	}


	//MERGE SORT
	public void mergeSort(){
		int[] tmpArray = new int[ ints.length ];
		mergeSort( ints, tmpArray, 0, ints.length - 1 );

	}

	private void mergeSort( int[]a, int[]tmpArray,int left, int right ) {
		if( left < right )
		{
			int center = ( left + right ) / 2;
			mergeSort( a, tmpArray, left, center );
			mergeSort( a, tmpArray, center + 1, right );
			merge( a, tmpArray, left, center + 1, right );
		}
	}
	private void merge( int[]a, int[]tmpArray, int leftPos, int rightPos, int rightEnd ) {
		int leftEnd = rightPos - 1;
		int tmpPos = leftPos;
		int numElements = rightEnd - leftPos + 1;

		while(leftPos <= leftEnd && rightPos <= rightEnd)
		{
			if( a[leftPos]<=a[rightPos])
			{
				tmpArray[tmpPos++] = a[leftPos++];
			}
			else
			{
				tmpArray[tmpPos++] = a[rightPos++];
			}
		}

		while(leftPos <= leftEnd)  
		{
			tmpArray[tmpPos++] = a[leftPos++];
		}

		while(rightPos <= rightEnd) 
		{
			tmpArray[tmpPos++] = a[rightPos++];
		}

		for(int i = 0; i < numElements; i++, rightEnd--)
		{
			a[rightEnd] = tmpArray[rightEnd];
		}
	}

	//QUICK SORT
	public void quickSort() 
	{
		quickSort(ints, 0, ints.length - 1);
	}
	public void quickSort(int ints[], int start, int end)
	{
		int i = start;                        
		int k = end;                        
		if (end - start >= 1)     
		{
			int pivot = ints[start];  
			while (k > i) 
			{
				while (ints[i] <= pivot && i <= end && k > i) 
				{
					i++;  
				}
				while (ints[k] > pivot && k >= start && k >= i) 
				{
					k--;    
				}
				if (k > i)                              
					swap(ints, i, k);                   
				if(anythingExtra())
				{
					break;
				}
			}
			swap(ints, start, k);          
			quickSort(ints, start, k - 1);
			quickSort(ints, k + 1, end);   
		}
		else   
		{
			return;      
		}
	}


	public void swap(int ints[], int index1, int index2) 
	{
		int temp = ints[index1];      
		ints[index1] = ints[index2];   
		ints[index2] = temp;              
	}

	//SEQUENTIAL SEARCH
	//changed it to take in something in ConsoleState
	public int sequentialSearch(Object orig)
	{
		//System.out.println("made it to here");
		int i=(Integer)orig;
		int j = 0;
		while(j < ints.length){
			//System.out.println("here");
			if(ints[j] == i)
			{
				//System.out.println("Done");
				return j;
			}
			j++;
		}
		return -1;
	}

	//BINARYSEARCH
	public static int binarySearch(ArrayList<Integer> ints, Object o){
		return binarySearch(ints, o, 0, ints.size()-1);
	}

	private static int binarySearch(ArrayList<Integer> ints, Object key, int imin, int imax)
	{
		// calculate midpoint to cut set in half
		int imid = (imin + imax) / 2;

		// three-way comparison
		if (ints.get(imid) > (int)((Integer)(key)))
			// key is in lower subset
			return binarySearch(ints, key, imin, imid-1);
		else if (ints.get(imid) < (int)((Integer)(key)))
			// key is in upper subset
			return binarySearch(ints, key, imid+1, imax);
		else
			// key has been found
			return imid;
	}


	@Override
	public boolean addAll(Collection arg0) {
		// TODO Auto-generated method stub
		return false;
	}


	@Override
	public void clear() {
		// TODO Auto-generated method stub

	}


	@Override
	public boolean contains(Object arg0) {
		// TODO Auto-generated method stub
		return false;
	}


	@Override
	public boolean containsAll(Collection arg0) {
		// TODO Auto-generated method stub
		return false;
	}


	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return false;
	}


	@Override
	public Iterator iterator() {
		// TODO Auto-generated method stub
		return null;
	}


	@Override
	public boolean remove(Object arg0) {
		// TODO Auto-generated method stub
		return false;
	}


	@Override
	public boolean removeAll(Collection arg0) {
		// TODO Auto-generated method stub
		return false;
	}


	@Override
	public boolean retainAll(Collection arg0) {
		// TODO Auto-generated method stub
		return false;
	}


	@Override
	public int size() {
		// TODO Auto-generated method stub
		return 0;
	}


	@Override
	public Object[] toArray() {
		// TODO Auto-generated method stub
		return null;
	}


	@Override
	public Object[] toArray(Object[] arg0) {
		// TODO Auto-generated method stub
		return null;
	}

	public boolean anythingExtra()
	{
		return false;
	}
}